{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Tree Inorder Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: inorderTraversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的中序遍历"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树的根节点 <code>root</code> ，返回 <em>它的 <strong>中序</strong>&nbsp;遍历</em> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg\" style=\"height: 200px; width: 125px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,2,3]\n",
    "<strong>输出：</strong>[1,3,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目在范围 <code>[0, 100]</code> 内</li>\n",
    "\t<li><code>-100 &lt;= Node.val &lt;= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶:</strong>&nbsp;递归算法很简单，你可以通过迭代算法完成吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-tree-inorder-traversal](https://leetcode.cn/problems/binary-tree-inorder-traversal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-tree-inorder-traversal](https://leetcode.cn/problems/binary-tree-inorder-traversal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,null,2,3]', '[]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        ret = []\n",
    "        if root.left is not None:\n",
    "            ret.extend(self.inorderTraversal(root.left))\n",
    "        ret.append(root.val)\n",
    "        if root.right is not None:\n",
    "            ret.extend(self.inorderTraversal(root.right))\n",
    "            \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: 'TreeNode') -> 'List[int]':\n",
    "        stack = []\n",
    "        out = []\n",
    "        node = root\n",
    "        while (node is not None) or (len(stack) != 0):\n",
    "            while node is not None:\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "            if len(stack) != 0:\n",
    "                node = stack.pop()\n",
    "                out.append(node.val)\n",
    "                node = node.right\n",
    "        return out\n",
    "        \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        s = []\n",
    "        while root:\n",
    "            s.append(root)\n",
    "            root = root.left\n",
    "        res = []\n",
    "        while s:\n",
    "            n = s.pop()\n",
    "            res.append(n.val)\n",
    "            if n.right:\n",
    "                n = n.right\n",
    "                while n:\n",
    "                    s.append(n)\n",
    "                    n = n.left\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "        if(root == None):\n",
    "            print(None)\n",
    "            return []\n",
    "        \n",
    "        print(root.val)\n",
    "        \n",
    "        \n",
    "        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "# Recursion function         \n",
    "        # if root is None:\n",
    "        #     return []\n",
    "        # left = self.inorderTraversal(root.left) \n",
    "        # mid = [root.val]\n",
    "        # right = self.inorderTraversal(root.right)\n",
    "        # return left + mid + right\n",
    "        \n",
    "        if root is None:\n",
    "            return []\n",
    "        stack = []\n",
    "        res = []\n",
    "        def push(root):\n",
    "            if root is None:\n",
    "                return \n",
    "            stack.append(root)\n",
    "            push(root.left)\n",
    "            \n",
    "        push(root)\n",
    "        while(len(stack)>0):\n",
    "            node = stack.pop()\n",
    "            res.append(node.val)\n",
    "            if node.right is not None:\n",
    "                push(node.right)\n",
    "        return res\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        s = []\n",
    "        while root:\n",
    "            s.append(root)\n",
    "            root = root.left\n",
    "        res = []\n",
    "        while s:\n",
    "            n = s.pop()\n",
    "            res.append(n.val)\n",
    "            if n.right:\n",
    "                n = n.right\n",
    "                while n:\n",
    "                    s.append(n)\n",
    "                    n = n.left\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def tool(self, root , ls):\n",
    "        if root is None: return\n",
    "        if root.left: self.tool(root.left, ls)\n",
    "        ls.append(root.val)\n",
    "        if root.right: self.tool(root.right, ls)\n",
    "    def inorderTraversal(self, root: 'TreeNode') -> 'List[int]':\n",
    "        level_ls = self.tree2ls_level(root)\n",
    "        root = self.mk_tree(level_ls)\n",
    "        ls = []\n",
    "        self.tool(root, ls)\n",
    "        return ls\n",
    "    \n",
    "    # 层序遍历 用队列 无需迭代\n",
    "    def tree2ls_level(self, root: 'TreeNode'):\n",
    "        if root is None: return []\n",
    "        q = Queue()\n",
    "        q.put(root)\n",
    "        ls = []\n",
    "        while not q.empty():\n",
    "            cur = q.get()\n",
    "            if cur:\n",
    "                ls.append(cur.val)\n",
    "                q.put(cur.left)\n",
    "                q.put(cur.right)\n",
    "            else:\n",
    "                ls.append(None)\n",
    "        i = len(ls) - 1\n",
    "        while True:\n",
    "            if ls[i]: break\n",
    "            i -= 1\n",
    "        return ls[:i+1]\n",
    "\n",
    "    # 层序重建\n",
    "    def mk_tree(self, ls):\n",
    "        len_ls = len(ls)\n",
    "        if len_ls == 0: return None\n",
    "        cur = root = TreeNode(ls[0])\n",
    "        node_ls, front, i = [cur], 0, 1\n",
    "        while i < len(ls):\n",
    "            node = node_ls[front]\n",
    "            front += 1\n",
    "            item = ls[i]\n",
    "            i += 1\n",
    "            if item is not None:\n",
    "                new_n = TreeNode(item)\n",
    "                node.left = new_n\n",
    "                node_ls.append(new_n)\n",
    "\n",
    "            if i >= len(ls): break\n",
    "\n",
    "            item = ls[i]\n",
    "            i += 1\n",
    "            if item is not None:\n",
    "                new_n = TreeNode(item)\n",
    "                node.right = new_n\n",
    "                node_ls.append(new_n)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        stack = []\n",
    "        if root:\n",
    "            stack.append(root)\n",
    "\n",
    "        while stack:\n",
    "            top = stack[-1]\n",
    "            if top.left is not None:\n",
    "                stack.append(top.left)\n",
    "                top.left = None\n",
    "\n",
    "            else:\n",
    "                now = stack.pop()\n",
    "                result.append(now.val)\n",
    "                if now.right is not None:\n",
    "                    stack.append(now.right)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    \n",
    "    def inorder(self,res,root):\n",
    "        if root == None:\n",
    "            return root\n",
    "        self.inorder(res,root.left)\n",
    "        res.append(root.val)\n",
    "        self.inorder(res,root.right)\n",
    "    \n",
    "    def inorder2(self,res,root):\n",
    "        if root == None:\n",
    "            return root\n",
    "        \n",
    "        stack = []\n",
    "        cur_node = root\n",
    "        while cur_node != None:\n",
    "            stack.append(cur_node)\n",
    "            cur_node = cur_node.left\n",
    "        \n",
    "        while True:\n",
    "            cur_node = stack.pop(-1)\n",
    "            res.append(cur_node.val)\n",
    "            \n",
    "            if cur_node.right != None:\n",
    "                cur_node = cur_node.right\n",
    "                while cur_node != None:\n",
    "                    stack.append(cur_node)\n",
    "                    cur_node = cur_node.left\n",
    "            \n",
    "            if len(stack) == 0:\n",
    "                break\n",
    "        \n",
    "    \n",
    "    def inorderTraversal(self, root):\n",
    "        res = []\n",
    "        self.inorder2(res,root)\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        res = []\n",
    "        stack = [root]\n",
    "        while len(stack) > 0:\n",
    "            curr = stack.pop()\n",
    "            if not isinstance(curr, TreeNode):\n",
    "                res.append(curr)\n",
    "                continue\n",
    "            if curr.right is not None:\n",
    "                stack.append(curr.right)\n",
    "            stack.append(curr.val)\n",
    "            if curr.left is not None:\n",
    "                stack.append(curr.left)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "\n",
    "        res = []\n",
    "        def helper(node,res):\n",
    "            if node == None:\n",
    "                return\n",
    "            helper(node.left,res)\n",
    "            res.append(node.val)\n",
    "            helper(node.right,res)\n",
    "        helper(root,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        def inorder(node, arr):\n",
    "            if node:\n",
    "                inorder(node.left, arr)\n",
    "                arr.append(node.val)\n",
    "                inorder(node.right, arr)\n",
    "        res = []\n",
    "        inorder(root, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        result = []\n",
    "        temp = []\n",
    "        while root or len(temp) != 0:\n",
    "            if root:\n",
    "                temp.append(root)\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = temp.pop()\n",
    "                result.append(root.val)\n",
    "                root = root.right\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        res = []\n",
    "        self.inorder(root, res)\n",
    "        return res\n",
    "\n",
    "\n",
    "    def inorder(self, root, res):\n",
    "        if not root:\n",
    "            return\n",
    "        self.inorder(root.left, res)\n",
    "        res.append(root.val)\n",
    "        self.inorder(root.right, res)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        result = []\n",
    "        stack = []\n",
    "        p = root\n",
    "        while stack or p:\n",
    "            while p:\n",
    "                stack.append(p)\n",
    "                p = p.left\n",
    "            p = stack.pop()\n",
    "            result.append(p.val)\n",
    "            p = p.right\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        if not root:return\n",
    "        res=[]\n",
    "        cur=root\n",
    "        stack=[]\n",
    "        while stack or cur:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur=cur.left\n",
    "            cur=stack.pop()\n",
    "            res.append(cur.val)\n",
    "            cur=cur.right\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        res = []\n",
    "        if root:\n",
    "            self.dfs(root,res)\n",
    "        return res\n",
    "\n",
    "    def dfs(self,root,res):\n",
    "        if root.left:\n",
    "            self.dfs(root.left, res)\n",
    "        res.append(root.val)\n",
    "        if root.right:\n",
    "            self.dfs(root.right,res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        # 递归\n",
    "        def inorder(node):\n",
    "            if not node:\n",
    "                return\n",
    "            stack.append(node)\n",
    "            if node.left:\n",
    "                inorder(node.left)\n",
    "            else:\n",
    "                res.append(stack.pop().val)\n",
    "                inorder(node.right)\n",
    "                while stack:\n",
    "                    last_node = stack.pop()\n",
    "                    res.append(last_node.val)\n",
    "                    inorder(last_node.right)\n",
    "            \n",
    "        res = []\n",
    "        stack = []\n",
    "        inorder(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        white, gray = 0, 1\n",
    "        res = []\n",
    "        stack = [(white, root)]\n",
    "        while stack:\n",
    "            print(stack)\n",
    "            color, node = stack.pop()\n",
    "            print(color, node)\n",
    "            if node is None:\n",
    "                continue\n",
    "            if color == white:\n",
    "                stack.append((white, node.right))\n",
    "                stack.append((gray, node))\n",
    "                stack.append((white, node.left))\n",
    "            else:\n",
    "                res.append(node.val)\n",
    "            print( stack)\n",
    "            print(res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return list()\n",
    "        from inspect import stack\n",
    "        res = list()\n",
    "        tmp_stack = list()\n",
    "        curr = root\n",
    "        while curr or tmp_stack:\n",
    "            while curr:\n",
    "                tmp_stack.append(curr)\n",
    "                curr = curr.left\n",
    "            curr = tmp_stack.pop()\n",
    "            res.append(curr.val)\n",
    "            curr = curr.right\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        def dfs(res,root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(res,root.left)\n",
    "            res.append(root.val)\n",
    "            dfs(res,root.right)\n",
    "        res = []\n",
    "        dfs(res,root)\n",
    "        return res\n",
    "\n",
    "        # def dfs(res,head):\n",
    "        #     if not head:\n",
    "        #         return\n",
    "        #     dfs(res,head.left)\n",
    "        #     res.append(head.val)\n",
    "        #     dfs(res,head.right)\n",
    "        # res = []\n",
    "        # dfs(res,root)\n",
    "        # return res\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root: return []\n",
    "        ret = []\n",
    "        stack = []\n",
    "        cur = root\n",
    "        while cur or stack:\n",
    "            if cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                ret.append(cur.val)\n",
    "                cur = cur.right\n",
    "           \n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorder(self, root: Optional[TreeNode], res):\n",
    "        if (root == None):\n",
    "            return\n",
    "        self.inorder(root.left, res)\n",
    "        res.append(root.val)\n",
    "        self.inorder(root.right, res)\n",
    "\n",
    "    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        res = []\n",
    "        self.inorder(root, res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def dfs(head):\n",
    "            if not head:\n",
    "                return []\n",
    "            res=[head.val]\n",
    "            return dfs(head.left)+res+dfs(head.right)\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        stack = []\n",
    "        order = []\n",
    "        current = root\n",
    "        left_done = False\n",
    "        if current is None:\n",
    "            return []\n",
    "        while True:\n",
    "            print(order)\n",
    "            if (not current.left is None) and (not left_done):\n",
    "                stack.append(current)\n",
    "                current = current.left\n",
    "                left_done = False\n",
    "            else:\n",
    "                order.append(current.val)\n",
    "                if not current.right is None:\n",
    "                    current = current.right\n",
    "                    left_done = False\n",
    "                else:\n",
    "                    if len(stack)>0:\n",
    "                        current = stack.pop()\n",
    "                        left_done = True\n",
    "                    else:\n",
    "                        print(\"S\")\n",
    "                        break\n",
    "        return order\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        res = []\n",
    "        stack = []\n",
    "        cur = root\n",
    "        while cur or stack:\n",
    "            if cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left \n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                res.append(cur.val)\n",
    "                cur = cur.right \n",
    "            print(cur,stack)\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        res = []\n",
    "        if not root:\n",
    "            return res\n",
    "        st = []\n",
    "        cur = root\n",
    "        while cur or st:\n",
    "            if cur:\n",
    "                st.append(cur)\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = st.pop()\n",
    "                res.append(cur.val)\n",
    "                cur = cur.right\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        stack = []\n",
    "        res = []\n",
    "        while root or stack:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            top = stack.pop()\n",
    "            res.append(top.val)\n",
    "            root = top.right\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        # 二叉树 递归\n",
    "        def midorder(node):\n",
    "            if not node:\n",
    "                return\n",
    "            midorder(node.left)\n",
    "            res.append(node.val)\n",
    "            midorder(node.right)\n",
    "        res = []\n",
    "        midorder(root)\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
